#include <stdio.h>

// wezly
typedef int node; // typ node (int)
void nodestab_print(node* , int, int ); // wydruk

// sortowania
#define key(A) (A) // wyznaczony klucz
#define less(A, B) (key(A) < key(B)) // porownywanie kluczy
#define exch(A, B) { node t = A; A = B; B = t; } // zamiana wezlow
#define compexch(A, B) if (less(B, A)) exch(A, B) // zamiana z porownaniem
#define bytesword 32
#define alpha 96
#define M 256 // klucze mniejsze od M
#define ch(A) digit(A, D)
#define alpha 96
#define m 256
#define ch(A) digit(A, D)
unsigned getbits(unsigned , int , int );
unsigned digit(node , int );
void insertion(node* , int , int );
void twrqsort(node* , int , int , int );

int main() 
{
  node nodestab[] = {1, 34, 10, 6, 8, 18, 5, 7, 23, 15}; // tablica wezlow
  int nnr = sizeof nodestab / sizeof(node ); // liczba wezlow
  twrqsort(nodestab, 0, nnr, 0); // sortowanie
  nodestab_print(nodestab, 0, nnr); // wydruk
  return 0;
}

// funkcje dla wezlow
void nodestab_print(node a[], int l, int r)
{
  int i;
  int x;
  for (i = l; i < r; i++) {
    x = a[i]; 
    printf("%i ", x);
  }
  printf("\n");
}

// funkcje dla sortowania
unsigned getbits(unsigned x, int p, int n)
{
  return (x>>(p+1-n))&~(~0<<n);
}

unsigned digit(node a, int d)
{
  return getbits(key(a)-alpha, d, 1);
}

void insertion(node a[], int l, int r)
{ 
  int i, j;
  node v;
  for (i = l + 1; i < r; i++) compexch(a[l], a[i]);
  for (i = l + 2; i < r; i++) { 
    j = i; 
    v = a[i]; 
    while (less(v, a[j-1]))
      { a[j] = a[j-1]; j--; }
    a[j] = v; 
  }  
}

void twrqsort(node a[], int l, int r, int D)
{ 
  int i, j, k, p, q; int v;
  if (r-l <= m) { 
    insertion(a, l, r); 
    return; 
  }
  v = ch(a[r]); i = l-1; j = r; p = l-1; q = r;
  while (i < j)
    { 
      while (ch(a[++i]) < v) ;
      while (v < ch(a[--j])) 
	if (j == l) break;
      if (i > j) break;
      exch(a[i], a[j]);
      if (ch(a[i])==v) { 
	p++; exch(a[p], a[i]); 
      }
      if (v==ch(a[j])) { 
	q--; exch(a[j], a[q]); 
      }
    }
  if (p == q) { 
    if (v != '\0') 
      twrqsort(a, l, r, D+1); 
    return; 
  }
  if (ch(a[i]) < v) i++;
  for (k = l; k <= p; k++, j--) 
    exch(a[k], a[j]);
  for (k = r; k >= q; k--, i++) 
    exch(a[k], a[i]);
  twrqsort(a, l, j, D);
  if ((i == r) && (ch(a[i]) == v)) 
    i++;
  if (v != '\0') 
    twrqsort(a, j+1, i-1, D+1); 
  twrqsort(a, i, r, D); 
}
